package leetcode_zh

import (
	"container/heap"
	"math"
	"math/rand"
	"sort"
	"strconv"
	"strings"
)

/**
 * @Description: 剑指 Offer II 060. 出现频率最高的 k 个数字 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/3 9:27
 **/
func topKFrequent(nums []int, k int) []int {
	var fre = make(map[int]int)
	for i := 0; i < len(nums); i++ {
		fre[nums[i]]++
	}

	var kh = &KHeap{}
	heap.Init(kh)
	for key, val := range fre {
		heap.Push(kh, [2]int{key, val})
		if kh.Len() > k {
			heap.Pop(kh)
		}
	}
	var res []int
	for _, val := range *kh {
		res = append(res, val[0])
	}
	return res
}

type KHeap [][2]int

func (h *KHeap) Push(x interface{}) {
	*h = append(*h, x.([2]int))
}
func (h *KHeap) Pop() interface{} {
	n := len(*h)
	x := (*h)[n-1]
	*h = (*h)[0 : n-1]
	return x
}
func (h KHeap) Len() int {
	return len(h)
}
func (h KHeap) Less(i, j int) bool {
	return h[i][1] < h[j][1]
}
func (h KHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

/**
 * @Description: 剑指 Offer II 077. 链表排序 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/3 10:08
 **/
func sortList077(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	var slow = head
	var fast = head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next
	}
	var mid = slow.Next
	slow.Next = nil
	var left = sortList077(head)
	var right = sortList077(mid)
	return mergeList(left, right)
}

func mergeList(node1, node2 *ListNode) *ListNode {
	var dummyHead = &ListNode{}
	var temp = dummyHead
	for node1 != nil && node2 != nil {
		if node1.Val < node2.Val {
			temp.Next = node1
			node1 = node1.Next
		} else {
			temp.Next = node2
			node2 = node2.Next
		}
		if temp.Next != nil {
			temp = temp.Next
		}
	}

	if node1 != nil {
		temp.Next = node1
	}
	if node2 != nil {
		temp.Next = node2
	}
	return dummyHead.Next
}

func sortList01(head *ListNode) *ListNode {
	return sort01(head, nil)
}
func sort01(head, tail *ListNode) *ListNode {
	if head == nil {
		return head
	}

	if head.Next == tail {
		head.Next = nil
		return head
	}

	slow, fast := head, head
	for fast != tail {
		slow = slow.Next
		fast = fast.Next
		if fast != tail {
			fast = fast.Next
		}
	}

	mid := slow
	return merge01(sort01(head, mid), sort01(mid, tail))
}

func merge01(head1, head2 *ListNode) *ListNode {
	dummyHead := &ListNode{}
	temp, temp1, temp2 := dummyHead, head1, head2
	for temp1 != nil && temp2 != nil {
		if temp1.Val <= temp2.Val {
			temp.Next = temp1
			temp1 = temp1.Next
		} else {
			temp.Next = temp2
			temp2 = temp2.Next
		}
		temp = temp.Next
	}
	if temp1 != nil {
		temp.Next = temp1
	} else if temp2 != nil {
		temp.Next = temp2
	}
	return dummyHead.Next
}

/**
 * @Description: 剑指 Offer II 058. 日程表 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/3 12:33
 **/

type MyCalendar struct {
	root *node
}

type node struct {
	start       int
	end         int
	left, right *node
}

func Constructor058() MyCalendar {
	return MyCalendar{
		root: &node{-1, 0, nil, nil},
	}
}

func insert058(start int, end int, root *node) bool {
	if end <= root.start {
		if root.left == nil {
			root.left = &node{start, end, nil, nil}
			return true
		}
		return insert058(start, end, root.left)
	} else if start >= root.end {
		if root.right == nil {
			root.right = &node{start, end, nil, nil}
			return true
		}
		return insert058(start, end, root.right)
	}
	return false
}

func (this *MyCalendar) Book(start int, end int) bool {
	return insert058(start, end, this.root)
}

/**
 * @Description: 剑指 Offer II 062. 实现前缀树 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/3 13:22
 **/

/** Initialize your data structure here. */
func Constructor062() Trie {
	return Trie{}
}

/** Inserts a word into the trie. */
func (this *Trie) Insert062(word string) {
	node := this
	for _, ch := range word {
		ch -= 'a'
		if node.children[ch] == nil {
			node.children[ch] = &Trie{}
		}
		node = node.children[ch]
	}
	node.isEnd = true
}

/** Returns if the word is in the trie. */
func (this *Trie) Search062(word string) bool {
	node := this.SearchPrefix(word)
	return node != nil && node.isEnd
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith062(prefix string) bool {
	return this.SearchPrefix062(prefix) != nil
}

func (this *Trie) SearchPrefix062(prefix string) *Trie {
	node := this
	for _, ch := range prefix {
		ch -= 'a'
		if node.children[ch] == nil {
			return nil
		}
		node = node.children[ch]
	}
	return node
}

/**
 * @Description: 剑指 Offer II 061. 和最小的 k 个数对 中等
 * @Keyword: 最小堆
 * @Author: kami
 * @Date: 2022/8/3 13:32
 **/
func kSmallestPairs(nums1, nums2 []int, k int) (ans [][]int) {
	m, n := len(nums1), len(nums2)
	h := hp{nil, nums1, nums2}
	for i := 0; i < k && i < m; i++ {
		h.data = append(h.data, pair{i, 0})
	}
	for h.Len() > 0 && len(ans) < k {
		p := heap.Pop(&h).(pair)
		i, j := p.i, p.j
		ans = append(ans, []int{nums1[i], nums2[j]})
		if j+1 < n {
			heap.Push(&h, pair{i, j + 1})
		}
	}
	return
}

type pair struct{ i, j int }
type hp struct {
	data         []pair
	nums1, nums2 []int
}

func (h hp) Len() int { return len(h.data) }
func (h hp) Less(i, j int) bool {
	a, b := h.data[i], h.data[j]
	return h.nums1[a.i]+h.nums2[a.j] < h.nums1[b.i]+h.nums2[b.j]
}
func (h hp) Swap(i, j int)       { h.data[i], h.data[j] = h.data[j], h.data[i] }
func (h *hp) Push(v interface{}) { h.data = append(h.data, v.(pair)) }
func (h *hp) Pop() interface{}   { a := h.data; v := a[len(a)-1]; h.data = a[:len(a)-1]; return v }

/**
 * @Description: 剑指 Offer II 017. 含有所有字符的最短字符串 困难
 * @Keyword: map
 * @Author: kami
 * @Date: 2022/8/5 7:34
 **/
func minWindow(s string, t string) string {
	minLeft, minRight := 0, -1 //标记最小区间，-1包含了未找到的情况
	ht := map[byte]int{}       //用哈希表记录窗口和t匹配数量

	for i := 0; i < len(t); i++ {
		ht[t[i]]++
	}

	charNum := len(ht)                                 // t 中未匹配字符数量
	for left, right := 0, 0; right < len(s); right++ { // 窗口指针
		if _, ok := ht[s[right]]; ok { // 如果是 t 中字符
			ht[s[right]]--
			if ht[s[right]] == 0 {
				charNum--
			}

			if charNum == 0 {
				for left < right { // 增加窗口的左边界, 缩小窗口尺寸
					if v, ok := ht[s[left]]; ok {
						if v < 0 { //负数表示窗口包含多余的字符，可以继续缩小
							ht[s[left]]++
						} else { //否则，此时的窗口不能再缩小
							break
						}
					}
					left++
				}

				// 与之前窗口比较，记录最小的窗口
				if minRight < 0 || minRight-minLeft > right-left {
					minLeft = left
					minRight = right
				}
			}
		}
	}

	return s[minLeft : minRight+1]
}

/**
 * @Description: 剑指 Offer II 098. 路径的数目 中等
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/8/5 11:33
 **/
func uniquePaths098(m int, n int) int {
	// dp[i][j] 到达i，j点的路径的个数
	var dp = make([][]int, m)
	for i := 0; i < m; i++ {
		dp[i] = make([]int, n)
	}
	for i := 0; i < n; i++ {
		dp[0][i] = 1
	}
	for i := 0; i < m; i++ {
		dp[i][0] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}

	return dp[m-1][n-1]
}

/**
 * @Description: 剑指 Offer II 063. 替换单词 中等
 * @Keyword: 前缀树
 * @Author: kami
 * @Date: 2022/8/5 11:44
 **/
func replaceWords(dictionary []string, sentence string) string {
	dictionarySet := map[string]bool{}
	for _, s := range dictionary {
		dictionarySet[s] = true
	}
	words := strings.Split(sentence, " ")
	for i, word := range words {
		for j := 1; j <= len(word); j++ {
			if dictionarySet[word[:j]] {
				words[i] = word[:j]
				break
			}
		}
	}
	return strings.Join(words, " ")
}

/**
 * @Description: 剑指 Offer II 064. 神奇的字典 中等
 * @Keyword:
 * @Author: kami
 * @Date:   11:21
 **/
type MagicDictionary struct {
	exist map[int]map[string]struct{}
}

/** Initialize your data structure here. */
func Constructor064() MagicDictionary {
	return MagicDictionary{
		exist: make(map[int]map[string]struct{}),
	}
}

func (this *MagicDictionary) BuildDict(dictionary []string) {
	for i := 0; i < len(dictionary); i++ {
		if m, ok := this.exist[len(dictionary[i])]; ok {
			m[dictionary[i]] = struct{}{}
		} else {
			var tmp = map[string]struct{}{
				dictionary[i]: {},
			}
			this.exist[len(dictionary[i])] = tmp
		}
	}
}

func (this *MagicDictionary) Search(searchWord string) bool {
	if m, ok := this.exist[len(searchWord)]; ok {
		var tmpKey = []byte(searchWord)
		var old byte
		for key, _ := range m {
			for i := 0; i < len(key); i++ {
				if tmpKey[i] != key[i] {
					old = tmpKey[i]
					tmpKey[i] = key[i]
					if _, yes := m[string(tmpKey)]; yes {
						return true
					} else {
						tmpKey[i] = old
						break
					}
				}
			}
		}
	}
	return false
}

/**
 * @Description: 剑指 Offer II 065. 最短的单词编码 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/6 17:01
 **/
func minimumLengthEncoding(words []string) int {
	var exist = make(map[string]struct{})
	for i := 0; i < len(words); i++ {
		exist[words[i]] = struct{}{}
	}
	for i := 0; i < len(words); i++ {
		for j := 1; j < len(words[i]); j++ {
			delete(exist, words[i][j:])
		}
	}
	var cnt = len(exist)
	for key, _ := range exist {
		cnt += len(key)
	}
	return cnt
}

/**
 * @Description: 剑指 Offer II 066. 单词之和 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/7 10:46
 **/
type MapSum struct {
	val        int
	preFixASum int
	isEnd      bool
	children   [26]*MapSum
}

/** Initialize your data structure here. */
func Constructor066() MapSum {
	return MapSum{}
}

func (this *MapSum) Insert(key string, val int) {
	var node = this
	node.preFixASum = -val
	for i := 0; i < len(key); i++ {
		var ch = key[i] - 'a'
		if node.children[ch] == nil {
			node.children[ch] = &MapSum{}
		}
		node.preFixASum += val
		node = node.children[ch]
	}
	// 重复键，则更新前缀和

	if node.isEnd {
		var oldVal = node.val
		var tmp = this
		tmp.preFixASum = -oldVal
		for i := 0; i < len(key); i++ {
			var ch = key[i] - 'a'
			if tmp.children[ch] == nil {
				tmp.children[ch] = &MapSum{}
			}
			tmp.preFixASum -= oldVal
			tmp = tmp.children[ch]
		}
		node.preFixASum += val - oldVal
	} else {
		node.preFixASum += val
	}
	node.val = val
	node.isEnd = true
}

func (this *MapSum) Sum(prefix string) int {
	node := this
	for i := 0; i < len(prefix); i++ {
		var ch = prefix[i] - 'a'
		if node.children[ch] == nil {
			return 0
		}
		node = node.children[ch]
	}
	return node.preFixASum
}

/**
 * @Description: 剑指 Offer II 067. 最大的异或  中等
 * @Keyword: 前缀树
 * @Author: kami
 * @Date: 2022/8/7 12:00
 **/
type Trie067 struct {
	kid [2]*Trie067
}

func findMaximumXOR(nums []int) (res int) {
	tire := &Trie067{}
	insert067(nums, tire)
	for _, val := range nums {
		node := tire
		k := 0
		for i := 31; i >= 0; i-- {
			v := 1 - val>>i&1
			if node.kid[v] != nil {
				node = node.kid[v]
				k += pow(2, i)
			} else {
				node = node.kid[1-v]
			}
		}
		res = getMax(res, k)
	}
	return
}

func insert067(nums []int, tire *Trie067) {
	for _, val := range nums {
		node := tire
		for i := 31; i >= 0; i-- {
			v := val >> i & 1
			if node.kid[v] == nil {
				node.kid[v] = &Trie067{}
			}
			node = node.kid[v]
		}
	}
}

func pow(k, v int) int {
	res := 1
	for i := 0; i < v; i++ {
		res *= k
	}
	return res
}

/**
 * @Description: 剑指 Offer II 070. 排序数组中只出现一次的数字 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/8 13:18
 **/
func singleNonDuplicate(nums []int) int {
	// 当 mid 是偶数时，mid+1=mid⊕1；
	//当mid 是奇数时，mid−1=mid⊕1。

	var left = 0
	var right = len(nums) - 1
	for left < right {
		var mid = (left + right) / 2
		if nums[mid] == nums[mid^1] {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return nums[left]
}

func singleNonDuplicate01(nums []int) int {
	low, high := 0, len(nums)-1
	for low < high {
		mid := low + (high-low)/2
		mid -= mid & 1
		if nums[mid] == nums[mid+1] {
			low = mid + 2
		} else {
			high = mid
		}
	}
	return nums[low]
}

/**
 * @Description: 剑指 Offer II 071. 按权重生成随机数 中等
 * @Keyword: 范围
 * @Author: kami
 * @Date: 2022/8/9 7:56
 **/
type Solution struct {
	pre []int
}

func Constructor071(w []int) Solution {
	for i := 1; i < len(w); i++ {
		w[i] += w[i-1]
	}
	return Solution{w}
}

func (s *Solution) PickIndex() int {
	x := rand.Intn(s.pre[len(s.pre)-1]) + 1
	return sort.SearchInts(s.pre, x)
}

/**
 * @Description: 剑指 Offer II 073. 狒狒吃香蕉 中等
 * @Keyword: 二分
 * @Author: kami
 * @Date: 2022/8/9 8:12
 **/
func minEatingSpeed(piles []int, h int) int {

	var maxH = piles[0]
	for i := 1; i < len(piles); i++ {
		if piles[i] > maxH {
			maxH = piles[i]
		}
	}

	var left = 1
	var right = maxH

	for left < right {
		var mid = (left + right) / 2
		var minH int
		for _, pile := range piles {
			minH += (pile-1)/mid + 1
		}
		if minH > h {
			left = mid + 1
		} else {
			right = mid
		}
	}

	return left
}

/**
 * @Description: 剑指 Offer II 079. 所有子集 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/10 9:12
 **/
func subsets079(nums []int) [][]int {
	var res [][]int

	var traceBack func(nums, cur []int, idx int)

	traceBack = func(nums, cur []int, idx int) {
		var tmp = make([]int, len(cur))
		copy(tmp, cur)
		res = append(res, tmp)

		for i := idx; i < len(nums); i++ {
			cur = append(cur, nums[idx])
			traceBack(nums, cur, i+1)
			cur = cur[0 : len(cur)-1]
		}
	}

	traceBack(nums, []int{}, 0)
	return res
}

/**
 * @Description: 剑指 Offer II 080. 含有 k 个元素的组合 中等
 * @Keyword: 回溯
 * @Author: kami
 * @Date: 2022/8/10 9:42
 **/
func combine(n int, k int) [][]int {
	var res [][]int

	var traceBack func(start, n, k int, cur []int)
	traceBack = func(start, n, k int, cur []int) {
		if len(cur) == k {
			var tmp = make([]int, k)
			copy(tmp, cur)
			res = append(res, tmp)
			return
		}

		for i := start; i <= n; i++ {
			cur = append(cur, i)
			traceBack(i+1, n, k, cur)
			cur = cur[0 : len(cur)-1]
		}
	}

	traceBack(1, n, k, []int{})
	return res
}

/**
 * @Description: 剑指 Offer II 116. 省份数量 中等
 * @Keyword: 递归 并查集
 * @Author: kami
 * @Date: 2022/8/10 9:49
 **/
func findCircleNum(isConnected [][]int) int {
	var ans int
	vis := make([]bool, len(isConnected))
	var dfs func(int)
	// 深度优先遍历
	dfs = func(from int) {
		vis[from] = true
		for to, conn := range isConnected[from] {
			if conn == 1 && !vis[to] {
				dfs(to)
			}
		}
	}

	for i, v := range vis {
		if !v {
			ans++
			dfs(i)
		}
	}
	return ans

}

// 广度优先遍历
func findCircleNum001(isConnected [][]int) (ans int) {
	vis := make([]bool, len(isConnected))
	for i, v := range vis {
		if !v {
			ans++
			queue := []int{i}
			for len(queue) > 0 {
				from := queue[0]
				queue = queue[1:]
				vis[from] = true
				for to, conn := range isConnected[from] {
					if conn == 1 && !vis[to] {
						queue = append(queue, to)
					}
				}
			}
		}
	}
	return
}

func findCircleNum116(isConnected [][]int) int {
	parent := make([]int, len(isConnected))
	for i := 0; i < len(isConnected); i++ {
		parent[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
	group := len(isConnected)
	union := func(x, y int) {
		a, b := find(x), find(y)
		if a == b {
			return
		}
		parent[b] = a
		group--
	}

	for i := 0; i < len(isConnected); i++ {
		for j := i + 1; j < len(isConnected); j++ {
			if isConnected[i][j] == 1 {
				union(i, j)
			}
		}
	}

	return group
}

/**
 * @Description: 剑指 Offer II 094. 最少回文分割 困难
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/8/10 13:42
 **/
func minCut(s string) int {
	n := len(s)
	g := make([][]bool, n)
	for i := range g {
		g[i] = make([]bool, n)
		for j := range g[i] {
			g[i][j] = true
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			g[i][j] = s[i] == s[j] && g[i+1][j-1]
		}
	}

	f := make([]int, n)
	for i := range f {
		if g[0][i] {
			continue
		}
		f[i] = math.MaxInt64
		for j := 0; j < i; j++ {
			if g[j+1][i] && f[j]+1 < f[i] {
				f[i] = f[j] + 1
			}
		}
	}
	return f[n-1]
}

/**
 * @Description: 剑指 Offer II 097. 子序列的数目 困难
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/8/11 13:08
 **/
func numDistinct(s string, t string) int {
	if len(s) < len(t) {
		return 0
	}
	var ns = len(s)
	var nt = len(t)

	var dp = make([][]int, ns+1)
	for i := 0; i <= ns; i++ {
		dp[i] = make([]int, nt+1)
		dp[i][0] = 1
	}

	for i := 1; i <= ns; i++ {
		for j := 1; j <= nt; j++ {
			var cnt int
			if s[i-1] == t[j-1] {
				cnt = dp[i-1][j-1]
			}
			dp[i][j] = dp[i-1][j] + cnt
		}
	}

	return dp[ns][nt]
}

/**
 * @Description: 剑指 Offer II 078. 合并排序链表 困难
 * @Keyword: 分割 归并
 * @Author: kami
 * @Date: 2022/8/11 13:56
 **/
func mergeKLists078(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}
	if len(lists) == 2 {
		return mergeList(lists[0], lists[1])
	}
	var half = len(lists) / 2
	var left = mergeKLists078(lists[0:half])
	var right = mergeKLists078(lists[half:])

	return mergeList(left, right)
}

/**
 * @Description: 剑指 Offer II 039. 直方图最大矩形面积 困难
 * @Keyword: 左右指针
 * @Author: kami
 * @Date: 2022/8/11 14:09
 **/
func largestRectangleArea(heights []int) int {
	var max int
	var left int
	var right int
	for i := 0; i < len(heights); i++ {
		if heights[i]*len(heights) > max {
			for left >= 0 && heights[left] >= heights[i] {
				left--
			}
			for right < len(heights) && heights[right] >= heights[i] {
				right++
			}
			max = getMax(max, (right-left-1)*heights[i])
		}
	}
	return max
}

/**
 * @Description: 剑指 Offer II 112. 最长递增路径 困难
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/8/11 16:02
 **/
func longestIncreasingPath(matrix [][]int) int {
	var dp = make([][]int, len(matrix))
	for i := 0; i < len(matrix); i++ {
		dp[i] = make([]int, len(matrix[i]))
	}
	var max int
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[i]); j++ {
			var cur = dfsPath(matrix, dp, i, j)
			if cur > max {
				max = cur
			}
		}
	}
	return max - 1
}

func dfsPath(matrix, dp [][]int, i, j int) int {
	if i < 0 || i == len(matrix) || j < 0 || j == len(matrix[0]) {
		return 0
	}
	if dp[i][j] > 0 {
		return dp[i][j]
	}
	var up, down, left, right int
	// 上
	if i-1 >= 0 && matrix[i-1][j] > matrix[i][j] {
		up = dfsPath(matrix, dp, i-1, j)
		dp[i-1][j] = up
	}
	// 下
	if i+1 < len(matrix) && matrix[i+1][j] > matrix[i][j] {
		down = dfsPath(matrix, dp, i+1, j)
		dp[i+1][j] = down
	}
	// 左
	if j-1 >= 0 && matrix[i][j-1] > matrix[i][j] {
		left = dfsPath(matrix, dp, i, j-1)
		dp[i][j-1] = left
	}
	// 右
	if j+1 < len(matrix[0]) && matrix[i][j+1] > matrix[i][j] {
		right = dfsPath(matrix, dp, i, j+1)
		dp[i][j+1] = right
	}

	dp[i][j] = getMax(up, down, left, right) + 1

	return dp[i][j]
}

/**
 * @Description: 剑指 Offer II 040. 矩阵中最大的矩形 困难
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/12 7:57
 **/
func maximalRectangle(matrix []string) (ans int) {
	if len(matrix) == 0 {
		return
	}
	m, n := len(matrix), len(matrix[0])
	left := make([][]int, m)
	for i, row := range matrix {
		left[i] = make([]int, n)
		for j, v := range row {
			if v == '0' {
				continue
			}
			if j == 0 {
				left[i][j] = 1
			} else {
				left[i][j] = left[i][j-1] + 1
			}
		}
	}
	for i, row := range matrix {
		for j, v := range row {
			if v == '0' {
				continue
			}
			width := left[i][j]
			area := width
			for k := i - 1; k >= 0; k-- {
				width = min(width, left[k][j])
				area = getMax(area, (i-k+1)*width)
			}
			ans = getMax(ans, area)
		}
	}
	return
}

/**
 * @Description: 剑指 Offer II 048. 序列化与反序列化二叉树 困难
 * @Keyword: 深度优先
 * @Author: kami
 * @Date: 2022/8/12 8:28
 **/
type Codec struct{}

func Constructor048() (_ Codec) {
	return
}

func (Codec) serialize(root *TreeNode) string {
	sb := &strings.Builder{}
	var dfs func(*TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil {
			sb.WriteString("null,")
			return
		}
		sb.WriteString(strconv.Itoa(node.Val))
		sb.WriteByte(',')
		dfs(node.Left)
		dfs(node.Right)
	}
	dfs(root)
	return sb.String()
}

func (Codec) deserialize(data string) *TreeNode {
	sp := strings.Split(data, ",")
	var build func() *TreeNode
	build = func() *TreeNode {
		if sp[0] == "null" {
			sp = sp[1:]
			return nil
		}
		val, _ := strconv.Atoi(sp[0])
		sp = sp[1:]
		return &TreeNode{val, build(), build()}
	}
	return build()
}

/**
 * @Description: 剑指 Offer II 051. 节点之和最大的路径 困难
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/8/12 8:59
 **/
func maxPathSum051(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var max = root.Val

	var dfs func(node *TreeNode) int

	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		var sum = node.Val
		var left = dfs(node.Left)
		if left < 0 {
			left = 0
		}
		var right = dfs(node.Right)
		if right < 0 {
			right = 0
		}
		var tmpSum = sum + left + right
		if tmpSum > max {
			max = tmpSum
		}

		if left > right {
			sum += left
		} else {
			sum += right
		}

		return sum
	}

	dfs(root)
	return max
}

/**
 * @Description: 剑指 Offer II 108. 单词演变 困难
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/13 8:15
 **/
func ladderLength(beginWord string, endWord string, wordList []string) int {
	// 单词：id
	wordId := map[string]int{}
	// id下标：邻居单词的id
	graph := [][]int{}
	// 添加id
	addWord := func(word string) int {
		id, has := wordId[word]
		if !has {
			id = len(wordId)
			wordId[word] = id
			// 初始化
			graph = append(graph, []int{})
		}
		return id
	}

	addEdge := func(word string) int {
		id1 := addWord(word)
		s := []byte(word)
		for i, b := range s {
			s[i] = '*'
			id2 := addWord(string(s))
			graph[id1] = append(graph[id1], id2)
			graph[id2] = append(graph[id2], id1)
			s[i] = b
		}
		return id1
	}

	for _, word := range wordList {
		addEdge(word)
	}
	beginId := addEdge(beginWord)
	endId, has := wordId[endWord]
	if !has {
		return 0
	}

	const inf int = math.MaxInt64
	dist := make([]int, len(wordId))
	for i := range dist {
		dist[i] = inf
	}
	/*
		最后我们将起点加入队列开始广度优先搜索，当搜索到终点时，我们就找到了最短路径的长度。
		注意因为添加了虚拟节点，所以我们得到的距离为实际最短路径长度的两倍。
		同时我们并未计算起点对答案的贡献，所以我们应当返回距离的一半再加一的结果。
	*/
	dist[beginId] = 0
	queue := []int{beginId}
	for len(queue) > 0 {
		v := queue[0]
		queue = queue[1:]

		if v == endId {
			return dist[endId]/2 + 1
		}
		// 邻居单词id
		for _, w := range graph[v] {
			if dist[w] == inf {
				dist[w] = dist[v] + 1
				queue = append(queue, w)
			}
		}
	}

	return 0
}

/**
 * @Description: 剑指 Offer II 114. 外星文字典 困难
 * @Keyword:
 * @Author: kami
 * @Date: 2022/8/13 17:56
 **/
func alienOrder(words []string) string {
	graph, set, d := map[byte][]byte{}, map[byte]bool{}, make([]int, 26)
out:
	for i, word := range words {
		for j := range word {
			set[word[j]] = true
		}
		if i < len(words)-1 {
			for j := 0; j < min(len(words[i]), len(words[i+1])); j++ {
				if words[i][j] != words[i+1][j] {
					graph[words[i][j]] = append(graph[words[i][j]], words[i+1][j])
					d[words[i+1][j]-'a']++
					continue out
				}
			}
			if len(words[i]) > len(words[i+1]) {
				return ""
			}
		}
	}
	ans := []byte{}
	for s := range set {
		if d[s-'a'] == 0 {
			ans = append(ans, s)
		}
	}
	for i := 0; i < len(ans); i++ {
		for _, nxt := range graph[ans[i]] {
			d[nxt-'a']--
			if d[nxt-'a'] == 0 {
				ans = append(ans, nxt)
			}
		}
	}
	if len(ans) == len(set) {
		return string(ans)
	}
	return ""
}

/**
 * @Description: 剑指 Offer II 117. 相似的字符串 困难
 * @Keyword: 并查集
 * @Author: kami
 * @Date: 2022/8/13 18:39
 **/
type unionFind struct {
	parent, size []int
	setCount     int // 当前连通分量数目
}

func newUnionFind(n int) *unionFind {
	parent := make([]int, n)
	size := make([]int, n)
	for i := range parent {
		parent[i] = i
		size[i] = 1
	}
	return &unionFind{parent, size, n}
}

func (uf *unionFind) find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *unionFind) union(x, y int) {
	fx, fy := uf.find(x), uf.find(y)
	if fx == fy {
		return
	}
	if uf.size[fx] < uf.size[fy] {
		fx, fy = fy, fx
	}
	uf.size[fx] += uf.size[fy]
	uf.parent[fy] = fx
	uf.setCount--
}

func (uf *unionFind) inSameSet(x, y int) bool {
	return uf.find(x) == uf.find(y)
}

func isSimilar(s, t string) bool {
	diff := 0
	for i := range s {
		if s[i] != t[i] {
			diff++
			if diff > 2 {
				return false
			}
		}
	}
	return true
}

func numSimilarGroups(strs []string) int {
	n := len(strs)
	uf := newUnionFind(n)
	for i, s := range strs {
		for j := i + 1; j < n; j++ {
			if !uf.inSameSet(i, j) && isSimilar(s, strs[j]) {
				uf.union(i, j)
			}
		}
	}
	return uf.setCount
}
